To address the problem that dark channel prior algorithm is invalid for sky region and the problem that the color of the restored image became darker, a single image dehazing algorithm based on sky segmentation was presented. Firstly, the segmentation algorithm based on edge detection was used to divide the original image into sky region and non-sky region. Then, based on the dark channel prior method, the estimation method for atmospheric light and transmittance was improved for the dehaze of non-sky region. Finally, the sky region was processed by an optimized contrast enhancement algorithm based on cost function. The experimental results demonstrate that, compared with dark channel prior algorithm, many technical specifications of restored images such as variance, average gradient and entropy are greatly improved. The proposed algorithm can effectively avoid the Halo effect in sky region and restore the true scene color while maintaining high operating efficiency.